package oj.oj_35;

public class Solution2 {
    public Node copyRandomList(Node head) {
        // 遍历老链表的每个结点，记为 cur，进行结点的复制（cur.val == node.val），新结点记为 node
        // 将 node 插入到 cur 的后边
        // 建立老结点到新结点的映射关系：cur.next == node
        Node cur = head;
        while (cur != null) {
            Node next = cur.next;
            // 复制
            Node node = new Node(cur.val);
            // 将 node 插入到 cur 的后边
            node.next = cur.next;
            cur.next = node;

            cur = next;
        }

        // 从头再次遍历（一组：一个老结点，记为 cur，一个新结点，记为 node）
        // 修改 node.random 的关系
        // node.random = cur.random 映射到对应的新结点
        // node.random = cur.random.next;
        cur = head;
        while (cur != null) {
            Node node = cur.next;

            if (cur.random != null) {
                node.random = cur.random.next;
            } else {
                node.random = null;     // 这句话其实可以省略
            }

            cur = node.next;    // 下一个老结点，不能是 cur.next，cur.next 是对应的新结点
        }

        // 不断一组一组地遍历，使用尾插的方式，将老结点和新结点尾插到合适的链表中
        Node oldHead = new Node(-1);
        Node oldLast = oldHead;

        Node newHead = new Node(-1);
        Node newLast = newHead;

        cur = head;
        while (cur != null) {
            Node node = cur.next;   // 这一组的新结点
            Node next = node.next;  //  记录下一个老结点的位置

            // 把 cur 尾插到 oldHead + oldLast 对应的链表中
            oldLast.next = cur;
            oldLast = cur;
            cur.next = null;

            // 把 node 尾插到 newHead + newLast 对应的链表中
            newLast.next = node;
            newLast = node;
            node.next = null;

            cur = next;
        }

        return newHead.next;
    }
}

